\appendix

\section{Protocol}
\label{app-protocol}

In this appendix, we describe the macros and functions that are part
of the protocol of our technique, used for implementing most of the
sequence functions.
\vskip 0.3cm\noindent
\defun {apply-key-function} {element key-function}

This function takes an element of the sequence and a function to apply
in order to obtain the object to use for comparison.  For performance
reasons, this function should be inlined.

A typical definition of this function might look like this:

{\small\begin{verbatim}
(defun apply-key-function (element key-function)
  (declare (optimize (speed 3) (debug 0) (safety 3)))
  (declare (type function key-function))
  (cond ((eq key-function #'identity)
         element)
        ((eq key-function #'car)
         (car element))
        ((eq key-function #'cdr)
         (cdr element))
        (t
         (funcall key-function element))))
\end{verbatim}}
\noindent
\defmacro {canonicalize-key} {key-var}

This macro takes a single argument which must be a variable that holds
the value of the \texttt{\&key} keyword argument.  Its role is to make
sure the contents of the variable is a function.  A typical
implementation might look like this:

{\small\begin{verbatim}
(defmacro canonicalize-key (key-var)
  `(cond ((null ,key-var)
          (setf ,key-var #'identity))
         ((not (functionp ,key-var))
          (setf ,key-var (fdefinition ,key-var)))
         (t nil)))
\end{verbatim}}
\noindent
\defmacro {with-key-function} {key-function-var \body body}

This macro takes a single argument which must be a variable that holds
the value of the canonicalized \texttt{\&key} keyword argument.  It is
used to duplicate \textit{body} for different typical values for the
\textit{key} argument to many sequence functions.  A typical
implementation of this macro looks like this:

{\small\begin{verbatim}
(defmacro with-key-function (key-function-var &body body)
  `(cond ((eq ,key-function-var #'identity)
          ,@body)
         ((eq ,key-function-var #'car)
          ,@body)
         ((eq ,key-function-var #'cdr)
          ,@body)
         (t
          ,@body)))
\end{verbatim}}

In each clause of the \texttt{cond} form in this macro, the inlined
version of the function \texttt{apply-key-function} will be simplified
in a different way by the compiler, resulting in a specialized loop.
\vskip 0.3cm\noindent
\defmacro {for-each-relevant-cons}\\
{(cons-var index-var list start end from-end) \body body}

This macro executes \textit{body} for each \emph{relevant
  \texttt{cons} cell}.  It takes into account the values of
\textit{start} and \textit{end} to restrict the execution to a
particular sub-sequence, and it takes into account the value of
\textit{from-end} to determine the order in which the relevant
\texttt{cons} cells are supplied to the \textit{body} code.  The
parameter \textit{cons-var} is the name of a variable that contains a
reference to the relevant \texttt{cons} cell for each execution of
\textit{body}.  Similarly, the parameter \textit{index-var} is the
name of a variable that contains the index of the particular
\texttt{cons} cell to be processed.

Because of the size of the definition of this macro, due mainly to the
code for processing \texttt{cons} cells in reverse order
\cite{Durand:2015:ELS:reverse}, we do not show its definition here.
\vskip 0.3cm\noindent
\defmacro {with-test-and-test-not}\\
{(test-var test-not-var) \body body}

The role of this macro is to supply certain special cases for the
possible values of the keyword parameters \texttt{test} and
\texttt{test-not} of a typical sequence function.  It is assumed that
it has already been verified that at most one of the two keyword
arguments has a value other than \texttt{nil}.  A typical
implementation might look like this:

{\small\begin{verbatim}
(defmacro with-test-and-test-not
    ((test-var test-not-var) &body body)
  `(cond ((null ,test-not-var)
          (locally (declare (type function ,test-var))
            (cond ((eq ,test-var #'eq)
                   ,@body)
                  ((eq ,test-var #'eql)
                   ,@body)
                  (t
                   ,@body))))
         ((null ,test-var)
          (locally (declare (type function ,test-not-var))
            (cond ((eq ,test-not-var #'eq)
                   ,@body)
                  ((eq ,test-not-var #'eql)
                   ,@body)
                  (t
                   ,@body))))
         (t nil)))
\end{verbatim}}
\noindent
\defmacro {with-from-end} {from-end-var \body body}

This macro duplicates \textit{body} for the two cases where the value
of the argument variable \textit{from-end-var} is either \emph{true}
or \emph{false}.  A typical implementation looks like this:

{\small\begin{verbatim}
(defmacro with-from-end (from-end-var &body body)
  `(if ,from-end-var
       (progn ,@body)
       (progn ,@body)))
\end{verbatim}}
\noindent
\defun {satisfies-two-argument-test-p}\\
{item element test test-not}

This function is typically inlined.  It provides special cases for
common values of the \texttt{test} and \texttt{test-not} keyword
arguments of a typical sequence function.  All but one of these cases
will be eliminated in each branch of the macro
\texttt{with-test-and-test-not} in which this function is located.  A
typical implementation might look like this:

{\small\begin{verbatim}
(defun satisfies-two-argument-test-p
    (item element test test-not)
  (declare (optimize (speed 3) (debug 0) (safety 3)))
  (cond ((null test-not)
         (locally (declare (type function test))
           (cond ((eq test #'eq)
                  (eq item element))
                 ((eq test #'eql)
                  (eql item element))
                 (t
                  (funcall test item element)))))
        ((null test)
         (locally (declare (type function test-not))
           (cond ((eq test-not #'eq)
                  (not (eq item element)))
                 ((eq test-not #'eql)
                  (not (eql item element)))
                 (t
                  (not (funcall test-not item element))))))
        (t nil)))
\end{verbatim}}
\noindent
\defmacro {for-each-relevant-element}\\
{element-var index-var vector start end\\
from-end \body body}

This macro is used to traverse the elements of a vector.  The argument
\textit{element-var} is a symbol that is bound to each element during
the execution of \textit{body}.  Similarly, \textit{element-var} is a
symbol that is bound to the index of the relevant element.  The
\textit{vector} argument is an expression that must evaluate to a
vector.  The arguments \textit{start} and \textit{end} are expressions
that evaluate to the two indices of the interval to traverse.
Finally, \texttt{from-end} is a generalized Boolean that indicates
whether the traversal is to be done from the end of the relevant
interval.  A typical implementation of this macro might look like
this:

{\small\begin{verbatim}
(defmacro for-each-relevant-element
    ((elementv indexv vector start end from-end)
     &body body)
  (let ((vectorv (gensym))
        (startv (gensym))
        (endv (gensym)))
    `(let ((,vectorv ,vector)
           (,startv ,start)
           (,endv ,end))
       (declare (type fixnum ,startv ,endv))
       (if ,from-end
           (loop for ,indexv downfrom (1- ,endv)
                   to ,startv
                 do (let ((,elementv
                            (aref ,vectorv ,indexv)))
                      ,@body))
           (loop for ,indexv from ,startv below ,endv
                 do (let ((,elementv
                            (aref ,vectorv ,indexv)))
                      ,@body))))))
\end{verbatim}}
\noindent
\defmacro {with-simple} {vector \body body}

This macro simply checks whether \textit{vector} is a
\texttt{simple-array}, and duplicates \textit{body} in each branch of
the test.  A typical implementation might look like this:

{\small\begin{verbatim}
(defmacro with-simple (vector &body body)
  `(if (typep ,vector 'simple-array)
       (progn ,@body)
       (progn ,@body)))
\end{verbatim}}
\noindent
\defmacro {with-vector-type} {vector-var \body body}

This macro duplicates \textit{body} for each possible value of
\texttt{array-upgraded-element-type} that the implementation provides.
It also provides a local definition for the macro \texttt{vref} which
we use instead of \texttt{aref} to access the elements of the vector
in \textit{body}.  If the compiler of the implementation is unable to
specialize \texttt{aref} according to the element type, then the
implementation may provide different definitions of the macro
\texttt{vref} for different element types.  Since the supported
element types vary from one implementation to another, we do not
provide an example of how this macro may be implemented.
